1. Field of the Invention
The present invention relates to an automatic wiring device and an automatic wiring method carried out by the device for use in a pattern design on an integrated circuit or a printed wiring board, and more particularly to an automatic wiring device and its automatic wiring method capable of obtaining a wiring route by peeling off another wiring in case of necessity, when performing wiring processing on the terminals remaining unconnected through the initial wiring processing.
2. Description of the Related Art
When performing a pattern design on an integrated circuit or a printed wiring board by the use of a computer system such as a CAD system or the like, circuit elements are arranged on the coordinate plane surface for wiring arrangement of pattern at first, and then a wiring route for connecting terminals that are input/output points of each circuit element is searched for, then to carry out wiring.
The wiring processing of the conventional pattern design technique of this kind has been performed as follows. As illustrated in FIG. 8, the rectangle of a wiring surface 801 is divided into unit cells at first. A given value (hereinafter, referred to as a cost value) is set in each unit cell. A cost value is uniformly set in every unit cell. In the example of FIG. 8, the cost value of each unit cell is defined as "1" uniformly.
Next, in a pair of terminals to be connected, a wiring route is obtained by the locus starting from a terminal and stepping every unit cell intervening between the terminals to the end of the other terminal. At this time, the cost value of each unit cell on the wiring route is accumulated. When there exist a plurality of wiring routes with respect to a given pair of terminals, a wiring route having the minimum accumulated cost value is determined as the wiring route of this pair. This searching method of a wiring route is called as a cost-attached labyrinth method.
If there has been another wiring connected already when acquiring a wiring route with respect to the given terminal pair, the wiring becomes an obstacle to the wiring route to be acquired. More specifically, a cost value will not be set in the unit cell through which the wiring is going, so that this unit cell cannot be selected as a through point of the wiring route.
FIG. 8 shows an example in the case of connecting the terminals "S" and "S" while detouring around the obstacle, the terminals "T" and "T", and the wiring "T-T" therebetween. In FIG. 8(A), the accumulated value of each cost value on the wiring route connecting the terminals "S" and "S" is attached to each unit cell except for the unit cell through which the wiring "T-T" connecting the terminals "T" and "T" is going. The minimum accumulated cost value on the wiring route between the terminals "S" and "S" is "10" as shown in FIG. 8. Therefore, the route "L10" indicated in FIG. 8(B) is determined as the wiring route between the terminals "S" and "S".
Wiring processing is actually performed along thus-determined wiring route, to connect the terminal pair.
No problem arises when all the terminal pairs can be connected by detouring around an obstacle as mentioned above, in the initial wiring processing. However, when there remains a terminal pair unconnected in the initial wiring processing and there exists no route capable of detouring around all the obstacles with respect to the same terminal pair, a wiring route to connect the terminal pair will cross another wiring to cause a short circuit. In this case, a wiring route is searched for, with the cost value set on the unit cell where another wiring is going through. The wiring crossed by the wiring route is peeled off in order to perform wiring processing on this wiring route. As a result, since the terminal pair turns into unconnected state, wiring processing will be again on this terminal pair after completion of the performing wiring processing.
FIG. 9 is a flow chart showing an operation of connecting the terminal pair that failed to be connected in the initial wiring processing.
Referring to FIG. 9, after necessary initial setting is done (Step 901), wiring processing is performed in accordance with the design rule, in other words, in a way such as to prevent from the crossing of the wiring routes to cause a short circuit (Step 902). At this time, a terminal pair having no routes capable of detouring around all the obstacles is left behind as an unconnected terminal pair.
It is judged whether the wiring has been completed on all the terminal pairs (Step 903). When there remains an unconnected terminal pair, one terminal of the unconnected terminal pair is selected as a candidate for processing (Step 904), and a cost value is set on every unit cell in the wiring permitted area, including the unit cells through which another connected wiring is going (Step 905).
Next, a wiring route connecting the terminal pair is searched for, regardless of the design rule, in other words, in a way such as to permit a short circuit to another wiring, and the wiring processing is performed along the obtained wiring route (Step 906). The other wiring crossed by the wiring route is peeled off at this time.
Rewiring processing for connecting the terminal pair is performed (Step 907), as for a terminal pair which had been connected by the wiring peeled off in Step 906. At this time, if there exists a wiring route capable of connecting the terminal pair by detouring around an obstacle, the wiring processing will be performed along this wiring route. If there exists no wiring route as mentioned above, the wiring processing from Step 904 to Step 907 will be repeated to the terminal pair as an unconnected terminal pair, like other unconnected terminal pairs.
FIG. 10 is a view for use in describing the wiring processing according to the above conventional automatic wiring method. As illustrated in FIG. 10(A), there exist the terminal pairs to be connected, "S, S" and "T, T", on the coordinate plane surface for wiring arrangement. Any wiring route should be determined in a way such as to prevent from the crossing of routes to cause a short circuit. In other words, any wiring route doesn't have a unit cell in common.
As illustrated in FIG. 10(B), assuming that the terminal pair "S, S" is connected with each other, the terminal pair "T, T" cannot be connected with each other without crossing the wiring "S-S" connecting the terminal pair "S, S" and shorting the same. Therefore, the terminal pair "T, T" remains unconnected, so that the wiring processing is performed on it from Step 904 and the later mentioned above. In other words, the wiring route "T-T" is determined with the short circuit permitted to the wiring "S-S", and the wiring processing is performed along the wiring route "T-T" after peeling off the wiring "S-S", as illustrated in FIG. 10(C). The wiring processing is performed on the terminal pair "S, S" again along the wiring route "S-S" capable of detouring around the wiring "T-T", as illustrated in FIG. 10(D).
However, the above-mentioned conventional automatic wiring method, in which a cost value is uniformly set in every unit cell in the wiring processing of the terminal pair remaining unconnected in the initial wiring processing, considers none of the difficulty in the rewiring processing of the wiring peeled off when another wiring must be peeled off. Therefore, when the wiring processing is performed on the terminal pair whose wiring was peeled off, it may happen that another wiring must be peeled off again. Since a terminal in the vicinity of the wiring prohibited area is under restriction as to the direction in which wiring can be extended, it is better to prevent from drawing a wiring route in the vicinity of a terminal. However, since there is no difference among the cost values, it may happen that a wiring route is set in the vicinity of a terminal as follows.
For example, when a wiring route running in the longitudinal direction is set on the coordinate plane surface for wiring arrangement as shown in FIG. 11, either the wiring "L11" or "L12" must be peeled off. In FIG. 11, the unit cells indicated by the oblique lines are wiring prohibited areas. There is, however, a possibility of setting the wiring route "L13" after peeling off the wiring "L11" as shown in FIG. 11(B), because of no difference among each cost value. In this case, the wiring "L13" must be peeled off in order to rewire the terminal "P5", which is a useless processing.
When a wiring route running in the longitudinal direction is set on the coordinate plane surface for wiring arrangement as shown in FIG. 12, the wiring route should cross the wiring "L14" somewhere inevitably. In FIG. 12, the unit cells indicated by oblique lines are wiring prohibited areas. However, there is a possibility of setting the wiring route "L15" passing through the unit cell adjacent to the terminal "P6" as illustrated in FIG. 12(B). In this case, the wiring "L15" must be peeled off in order to rewire the terminal "P6", which is a useless processing.
As mentioned above, when another wiring is peeled off in order to perform the wiring processing on the terminal pair remaining unconnected in the initial wiring processing, further another wiring may be peeled off again in some cases, in order to perform the rewiring processing on the terminal pair getting unconnected owing to the wiring thereof being peeled off, which is defective in efficiency.
Further, it may happen that the wiring processing in accordance with the design rule cannot be completed, because of circulating like a loop between the step of obtaining wiring by a certain wiring processing and the step of peeling off another wiring by the same wiring processing.
For example, on the coordinate plane surface for wiring arrangement as shown in FIG. 13, if the wiring route connecting the unconnected terminal pair "B, B" is drawn like the wiring route "B-B" as shown in FIG. 13(B), with the terminal pair "A, A" connected with each other in the initial wiring processing as shown in FIG. 13(A), the wiring "A-A" must be peeled off in order to carry out the wiring processing along the wiring route "B-B", as shown in FIG. 13(C). This time, if the wiring route connecting the terminal pair "A, A" getting unconnected, owing to the wiring "A-A" being peeled off, is drawn again like the wiring route "A-A" as shown in FIG. 13(D), the wiring "B-B" must be peeled off again, in order to carry out the wiring processing along this wiring route "A-A", as shown in FIG. 13(A). Thus, the wiring processing will circulate from FIG. 13(A) to FIG. 13(D) forever, without being completed.
This kind of the conventional automatic wiring method is disclosed in, for example, Japanese Patent Publication Laid-Open (Kokai) No. Heisei 2-61772 "Automatic Wiring Device", No. Heisei 4-236671 "Automatic Peeling and Rewiring Method", and Japanese Patent Publication Laid-Open (Kokai) No. Heisei 7-48221 "Route Searching Method".
The automatic wiring device disclosed in Japanese Patent Publication Laid-Open (Kokai) No. Heisei 2-61772 "Automatic Wiring Device" comprises a means for extracting an obstacle between the starting point to the end point of wiring that would be unconnected in the initial wiring processing and judging whether the obstacle is removable or not, a means for computing an index for estimating whether it is possible or not to connect the unconnected position by removing a certain segment of the wiring forming the obstacle, as for each segment of the connected wiring forming the obstacle, a means for creating a combination of the segments thereof to be removed, with the removing priority attached there, a means for deleting the relevant segments, and a means for saving the deleted route.
The automatic wiring method disclosed in Japanese Patent Publication Laid-Open (Kokai) No. Heisei 4-236671 "Automatic Peeling and Rewiring Method" comprises a step of extending each searching route from a terminal pair to be connected with each other to detect another wiring that may be an obstacle, a step of continuously extending the searching route indifferently to another wiring being shorted by the searching route, a step of establishing the extended searching route as a wiring route for connecting the terminal pair and peeling off another wiring that is an obstacle, and a step of rewiring another wiring turning unconnected by being peeled off.
The automatic wiring method disclosed in Japanese Patent Publication Laid-Open (Kokai) No. Heisei 7-48221 "Route Searching Method" comprises a means for attaching each label value, in a way of increasing by one in an ascending order, to each unit cell on a route connecting one terminal to the other terminal, a means for accumulating a label value obtained by adding a first increment value to the above-mentioned label value, as a label value of the route, if the above route comes across another connected route on a certain unit cell, and accumulating a label value obtained by adding a second increment value to the above-mentioned label value, as a label value of the route, if the route comes across none of the unconnected routes, and a means for establishing a route where the total of each label value is minimum, as a wiring route for the terminal pair. Each means repeats the above processing until a predetermined wiring route setting state is set while increasing the first and second increment values by the label value accumulating means.
In the above-mentioned conventional automatic wiring technique, however, manual operation is obliged to decide a wiring route, when the processing of peeling the connected wiring is repeated in order to do the wiring processing for a terminal pair unconnected in the initial wiring processing, thereby deteriorating the efficiency in the wiring processing.